package com.yusong.algorithm.link;


/**
 * 插入排序法
 */
public class Link92_2 {

    public static void main(String[] args) {
        int[] data = {1,2,3,4,5};
        ListNode node = ListNodeUtil.create(data);

        Link92_2 demo = new Link92_2();
        node = demo.reverseBetween2(node, 2, 4);
        ListNodeUtil.printNode(node);
    }

    /**
     * 变换箭头方向
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || m == n){
            return head;
        }
        ListNode dummyHead = new ListNode(-1, head);
        //m前置
        ListNode mPre = dummyHead;
        //从m开始到n
        int index = 1;
        while(index < m){
            mPre = mPre.next;
            index++;
        }
        ListNode preNode = mPre.next;
        ListNode curNode = preNode.next;
        ListNode thirdNode = curNode.next;
        while(index < n){
            curNode.next = preNode;

            preNode = curNode;
            curNode = thirdNode;
            if(null != curNode) {
                thirdNode = curNode.next;
            }

            index++;
        }

        ListNode tmp = curNode;
        mPre.next.next = tmp;

        mPre.next = preNode;
        return dummyHead.next;
    }


    /**
     插入法
     **/
    public ListNode reverseBetween2(ListNode head, int m, int n) {
        if(head == null || m == n){
            return head;
        }
        ListNode dummyHead = new ListNode(-1, head);
        //m前置
        ListNode mPre = dummyHead;
        //从m开始到n
        int index = 1;
        while(index < m){
            mPre = mPre.next;
            index++;
        }
        ListNode first = mPre.next;
        ListNode tmp = first;
        ListNode curNode = first.next;
        ListNode thirdNode = curNode.next;
        while(index < n){
            mPre.next = curNode;
            curNode.next = first;

            first = curNode;
            curNode = thirdNode;
            if(thirdNode != null)
            thirdNode = thirdNode.next;
            //ListNodeUtil.printNode(mPre);
            index++;
        }
        tmp.next = curNode;
        return dummyHead.next;
}

    /*public ListNode reverseBetween(ListNode head, int m, int n) {
        //当前节点的坐标
        int index = 1;
        //当前节点
        ListNode curNode = head;
        //当前节点的前置节点
        ListNode preNode = null;
        //需要反转的前一个节点
        ListNode startNode =head;
        ListNode firstNode =head;
        while(index <= n){
            if(index <= m){
                startNode = preNode;
                firstNode = curNode;
                preNode = curNode;
                curNode = curNode.next;
                index++;
                continue;
            }

            //交换当前节点与前置节点
            ListNode tmp = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = tmp;
            if(index == n){
                if(startNode != null ){
                    if(startNode.next != null){
                        startNode.next.next = curNode;
                    }
                    startNode.next = preNode;
                }else {
                    head = preNode;
                    firstNode.next = curNode;
                }

                break;
            }
            index++;

        }
        return head;
    }*/
}
